package cn.dapeng.tree.binary;

/**
 * 二叉树折纸问题
 * <p>
 * 拿出一张纸条， 对折N次，打印对折N次后的'折点'凹凸顺序
 * <p>
 * <p>
 * 顺序：就是二叉树的先序遍历的结果
 *
 * 规律：
 *      1. 头节点是'凹'折痕
 *      2. 所有左子树的头都是'凹'折痕
 *      3. 所有右子树的头都是‘凸’
 */
public class PageFolding {

    /**
     * 对折N次
     *
     * @param N
     */
    public static void print(int N) {
        process(1, N, false);
    }

    /**
     * 模拟二叉树先序遍历过程
     * @param index
     * @param N
     * @param flag
     */
    public static void process(int index, int N, boolean flag) {
        if (index > N) {
            return;
        }

        process(index + 1, N, true);
        System.out.print(flag == true ? "凹 " : "凸 ");
        process(index + 1, N, false);
    }

    public static void main(String[] args) {
        print(5);
    }

}
